/**
 * 
 */
package combinatorics;

import java.util.Arrays;

import utils.PrintUtils;

/**
 * @author Michael
 *
 */
public class PrintAllPermutations {

	public static void swap(int[] a, int i, int j) {
		assert (a != null);
		int tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}
	// permutation recursive
	public static void permutateR(int[] a, int index) {
		if (a.length == index) {
			for (int i = 0; i < a.length; ++i) {
				System.out.printf("%d ", a[i]);
			}
			System.out.println();
		}
		else {
			for (int i = index; i < a.length; ++i) {
				swap(a, i, index);
				permutateR(a, index + 1);
				swap(a, i, index);
			}
		}
	}
	
	public static void permutateWithoutDuplicates(int[] a) {
		Arrays.sort(a); // or hash
		permutateWithoutDuplicatesSortR(a, 0);
	}
	
	public static void permutateWithoutDuplicatesSortR(int[] a, int index) {
		if (a.length == index) {
			PrintUtils.printArray(a);
		}
		else {
			int last = -1;
			for (int i = index; i < a.length; ++i) {
				if (a[i] == last)
					continue;
				last = a[i];
				swap(a, index, i);
				permutateWithoutDuplicatesSortR(a, index + 1);
				swap(a, index, i);
			}
			
		}
	}
	/**
	 * 
	 */
	public PrintAllPermutations() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] a = new int[] { 0, 1, 2, 3, 0 };
	    permutateR(a, 0);
		//permutateWithoutDuplicates(a);

	}

}
